public class YangHuiTriangle { //递归实现杨辉三角
    public static int element1(int i,int j) {
        if(j ==0||i==j){
            return 1;
        }
        return element1(i-1,j)+element1(i-1,j-1);
    }
    public static int element2(int[][] arr,int i,int j){//递归优化
        if(j==0||i==j){
            arr[i][j]=1;
        }
        if(arr[i][j]!=0){
            return arr[i][j];
        }
        arr[i][j]=element2(arr,i-1,j)+element2(arr,i-1,j-1);
        return arr[i][j];
    }
    public static void print1(int n) {
        for (int i = 0; i < n; i++) {
            for (int j=0;j<=i;j++){
                System.out.printf("%-4d",element1(i,j));
            }
            System.out.println();
        }
    }
    public static void print2(int n){
        int[][] arr=new int[n][];
        for (int i = 0; i < n; i++) {
            arr[i]=new int[i+1];
        }
        for (int i = 0; i < n; i++) {
            for (int j=0;j<=i;j++){
                element2(arr,i,j);
                System.out.printf("%-4d",arr[i][j]);
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int n=5;
        print2(n);
    }
}
